import { Sort } from "../public/Sort"
import { DefaultCompare, ICompareFunction, CompareEnum } from "../public/Utils"

/**
 * 计数排序
 * 计数排序是一个分布式排序，它是用来排序整数的优秀算法。
 * 分布式排序使用已组织好的辅助数据结构，
 * 然后进行合并，得到排好序的数组。
 * 计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。
 * 在所有元素都计数完成后，临时数组已排好序并可迭代以构建排序后的结果数组。
 **/
 export class CountingSort<T> extends Sort<T> {
    constructor(array: Array<T> = [], compareFun: ICompareFunction = new DefaultCompare()) {
        super(array, compareFun)
    }
    sort(): Array<T> {
        //获取数组长度
        const { length } = this.array
        if (length < 2) {
            return this.array;
        }
        //找到待排序数组中的最大值
        const maxValue: T = this.array.reduce((a, b) => {
            return a > b ? a : b
        })

        //创建计数数组，数组长度为待排序数组的最大值+1
        const counts = new Array(<number>maxValue + 1)
        //遍历待排序数组，为计数数组赋值
        this.array.forEach((item) => {
            //以当前遍历到的元素值为索引将对应位置元素值初始化为0
            if (!counts[<number>item]) {
                counts[<number>item] = 0
            }
            //当前位置的值进行自增，顺便应对数组有重复值的情况，有重复值时当前位置的值必定大于1
            counts[<number>item]++
        })

        //声明一个变量用于数组最终排序
        let sortedIndex: number = 0
        //遍历计数数组，根据计数数组的元素位置对待排序数组进行排序
        counts.forEach((count, i) => {
            //如果当前遍历到的元素值大于0，则执行替换操作进行排序
            while (count > 0) {
                //将当前元素索引赋值给array的sortedIndex号元素，随后sortedIndex自增
                (<number>this.array[sortedIndex++]) = i
                count--
            }
        })

        return this.array;
    }

}

const CountingSortTest = (): void => {
    const array = [123, 424, 637, 154, 541,23435]
    const countingSort: Sort<Number> = new CountingSort<Number>(array)
    console.log(countingSort.sort());
}
CountingSortTest()